package newcoder_exp.justPractise;

import org.junit.Test;

public class NC44 {
    public class Solution {
        public boolean isMatch(String s, String p) {
            if (s == null || p == null) return false;
            char[] ss = s.toCharArray();
            char[] ps = p.toCharArray();
            int len1 = s.length();
            int len2 = p.length();
            
            boolean[][] f = new boolean[len1 + 1][len2 + 1];
            f[0][0] = true;
            for (int i = 1; i <= len2; i++) {
                f[0][i] = ps[i - 1] == '*' && f[0][i - 1];
            }
            //对于p为空串为s不为空的情况，默认为false
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (isAlpha(ps[j - 1])) {
                        f[i][j] = f[i - 1][j - 1] && ss[i - 1] == ps[j - 1];
                    } else if (ps[j - 1] == '?') {
                        f[i][j] = f[i - 1][j - 1];
                    } else {
                        f[i][j] = f[i - 1][j] || f[i - 1][j - 1];
                    }
                 }
            }
           return f[len1][len2];
        }

        public boolean isAlpha(char c) {
            return c >= 'a' && c <= 'z';
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.isMatch("ab","?*"));
        System.out.println(s.isMatch("aab", "d*a*b"));

        
    }
}
